package graph.question;

import graph.GraphNode;
import graph.graphtype.NoDirectGraph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-11 15:52:10
 */

public class Bfs {
    public void bfs(Queue<GraphNode> stack, List<Integer> result, int[] visited){
        if (!stack.isEmpty()){
            GraphNode tempNode = stack.poll();
            result.add(tempNode.id);
            visited[tempNode.id] = 1;

            while (tempNode.next != null){
                if (visited[tempNode.next.id] != 1){
                    visited[tempNode.next.id] = 1;
                    stack.add(tempNode.next.edgeNode);
                }
                tempNode = tempNode.next;
            }
            bfs(stack, result, visited);
        }
    }

    public List<Integer> bfs(NoDirectGraph g, int id){
        Queue<GraphNode> stack = new LinkedList<>();
        int[] visited = new int[g.table.length];
        List<Integer> result = new ArrayList<>();

        stack.add(g.table[id]);

        while (!stack.isEmpty()){
            GraphNode tempNode = stack.poll();
            result.add(tempNode.id);
            visited[tempNode.id] = 1;

            while (tempNode.next != null){
                if (visited[tempNode.next.id] != 1){
                    visited[tempNode.next.id] = 1;
                    stack.add(tempNode.next.edgeNode);
                }
                tempNode = tempNode.next;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {0, 4}, {1, 0}, {1, 3}, {2, 0}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 4}, {4, 0}, {4, 2}, {4, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};

        NoDirectGraph g = new NoDirectGraph(data.length, data);
        g.generateGraph(edges);

        List<Integer> result = new ArrayList<>();
        int[] visited = new int[data.length];
        Queue<GraphNode> stack = new LinkedList<>();
        stack.add(g.table[0]);
        // new Bfs().bfs(stack, result, visited);
        List<Integer> bfs = new Bfs().bfs(g, 0);

        System.out.println("result = " + result);



    }
}
